package com.gwcloud.leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode039 
* @author      : ganwei 
* @date        : 2020年5月6日 
* @Description : TODO 
*/
public class Leetcode0039 {
	List<List<Integer>> result = new ArrayList<>();
	int sum,k;
	/**
	 * -解题思路，果断回溯，现在回溯有点刷飘了
	 */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {   	
    	backtrack(candidates,target,new ArrayList<Integer>(),0, 0);

    	return result;
    }
    
    /**
     * 回溯主体函数
     */
    public void backtrack(int[] candidates,int target,List<Integer> li,int sum,int index) {

    	if(sum > target) {
    		return;	
    	}
    	if(target == sum) {
    		result.add(new ArrayList<Integer>(li));
    		return;
    	}
    	
    	for(int i = index; i < candidates.length; i++) {
    		li.add(candidates[i]);
    		backtrack(candidates,target,li,sum+candidates[i],i);
    		li.remove(li.size()-1);
    	}
    	
    }
    
    /**
     * 
     * @Title       : main 
     * @param       : @param args
     * @return      : void
     * @Description : TODO
     */
    public static void main(String[] args) {
    	
    }
}
